package com.itheima.datastructure.binarysearchtree.binarytree;

import com.itheima.datastructure.stack.LinkedListStack;

public class E05Leetcode104_2 {
    /*思路:
    使用非递归的后序遍历，栈的最大高度即为最大深度
     */
    public int maxDepth(TreeNode root){
        TreeNode curr=root;
        TreeNode pop=null;
        LinkedListStack<TreeNode> stack=new LinkedListStack<>(1000);
        int max=0;//栈的最大高度
        while(curr!=null || !stack.isEmpty()){
            if(curr!=null){
                stack.push(curr);
                int size=stack.getSize();
                if(size>max){
                    max=size;
                }
                curr=curr.left;
            }else{
                TreeNode peek=stack.peek();
                if(peek.right==null || peek.right==pop){
                    pop=stack.pop();
                }else{
                    curr=peek.right;
                }
            }
        }
        return max;
    }
}
